1. Field of the Invention
The present invention relates to cryptography and in particular to concepts for calculating a multiplication of a multiplier and a multiplicand with regard to a modulus within a cryptographical calculation, wherein the multiplier, the multiplicand and the modulus are parameters of the cryptographical calculation.
2. Description of the Related Art
Cryptography is one of the basic applications for modular arithmetic. One basic algorithm for cryptography is the known RSA algorithm. The RSA algorithm builds up on a modular exponentiation which may be illustrated as follows:C=Md mod (N).
Here, C is an encrypted message, M is a non-encrypted messaged, d is the secret key and M is the modulus. The modulus N is usually generated by a multiplication of two prime numbers p and q. The modular exponentiation is broken up into multiplications using the known square and multiply algorithm. For this, the exponent d is broken up into powers to two, so that the modular exponentiation may be broken up into several modular multiplications. In order to be able to implement the modular exponentiation in an efficient way regarding calculation, the modular exponentiation is therefore broken up into modular multiplications which may then be broken up into modular additions.
DE 3631992 C2 discloses a cryptography method wherein the modular multiplication may be accelerated using a multiplication look-ahead method and using a reduction look-ahead method. The method described in DE 3631992 C2 is also referred to as the ZDN method and is described in more detail with reference to FIG. 18. After a starting step 900 of the algorithm the global variables M, C and N are initialized. The aim is to calculate the following modular multiplication:Z=M*C mod N. 
M is referred to as the multiplier, while C is referred to as the multiplicand. Z is the result of the modular multiplication, while N is the modulus.
Hereupon different local variables are initialized which need not be explained in more detail here. In the following, two look-ahead methods are applied. In the multiplication look-ahead method GEN_MULT_LA using different look-ahead rules a multiplication shift value sZ and a multiplication look-ahead parameter a are calculated (910). Hereupon, the current content of the Z register is subjected to a left-shift operation by sz digits (920).
Substantially, in parallel to that a reduction look-ahead method GEN_Mod_LA (930) is performed to calculate a reduction shift value Sn and a reduction parameter b. In a step 940 the current content of the modulus register, that is N, is shifted to the left or to the right, respectively, by sn digits in order to generate a shifted modulus value N′. The central three operand operation of the ZDN method takes place in a step 950. Hereby, the intermediate result Z′ is added to the multiplicand C after step 920 which is multiplied with the multiplication look-ahead parameter a and to the shifted modulus N′ which is multiplied with the reduction look-ahead parameter b. Depending on the current situation the look-ahead parameters a and b may have a value of +1, 0 or −1.
One typical case is that the multiplication look-ahead parameter a is +1 and that the reduction look-ahead parameter is −1 so that to a shifted intermediate result Z′ the multiplicand C is added and the shifted modulus N′ is subtracted from the same. a will have a value equal 0 when the multiplication look-ahead method would allow more than one preset number of individual left shifts, that is when sz is greater than the maximum admissible value of sz, which is also referred to as k. For the case that a equals 0 and that Z′ is rather small due to the preceding modular reduction, that is the preceding subtraction of the shifted modulus, and is in particular smaller than the shifted modulus N′, no reduction need to take place, so that the parameter b is equal 0.
The steps 910 to 950 are performed until any digits of the multiplicand are processed, that is until m is equal 0, and until also a parameter n is equal 0 which indicates whether the shifted modulus N′ is even greater than the original modulus N, or whether despite the fact that already any digits of the multiplicand have been processed still further reduction steps need to be performed by subtracting the modulus from Z.
Finally it is determined whether Z is smaller than 0. If this is the case, the modulus N needs to be added to Z in order to achieve a final reduction, so that finally the correct result Z of the modular multiplication is obtained. In a step 960 the modular multiplication is ended using the ZDN method.
The multiplication shift value sZ and the multiplication parameter a which are calculated in step 910 by the multiplication look-ahead algorithm result from the topology of the multiplier and from the used look-ahead rules which are described in DE 3631992 C2.
The reduction shift value SN and the reduction parameter b are determined by a comparison of the current content of the Z register to a value ⅔ times N, as it is also described in DE 3631992 C2. Due to this comparison the name of a ZDN method results (ZDN=Zwei Drittel N=two thirds of N).
The ZDN method, as it is illustrated in FIG. 18, leads the modular multiplication to back a three operand addition (block 950 in FIG. 18), wherein for an increase of the calculation time efficiency the multiplication look-ahead method and along with it the reduction look-ahead method are used. Compared to the Montgomery reduction a calculation time advantage may be achieved.
In the following, with reference to FIG. 19 the reduction look-ahead method is explained in more detail which is implemented in block 930 of FIG. 18. First of all, in a block 1000 a reservation for the local variables is performed, i.e. the reduction look-ahead parameter b and the reduction shift value sn. In a block 1010 the reduction shift value sn is initialized to 0. Hereupon the value ZDN is calculated in a block 1020 which is equal to ⅔ of the modulus N. This value, which is determined in block 1020 is saved in a separate register on the crypto-coprocessor, the ZDN register.
In a block 1030 it is then determined whether the variable n is equal to 0 or whether the shift value SN is equal to −k. k is a value which defines the maximum shift value which is given by hardware. In the first run block 1030 is answered by NO, so that in a block 1030 the parameter n is decremented and that in a block 1060 also the reduction shift value is decremented by 1. Then, in block 1080 the variable ZDN is allocated again, that is with half its value, which may easily be achieved by a right shift of the value in the ZDN register. In block 1100 it is then determined whether the absolute value of the current intermediate result is greater than the value in the ZDN register.
This comparison operation in block 1100 is the central operation of the reduction look-ahead method. If the question is answered by YES, the iteration is ended and the reduction look-ahead parameter b is allocated, as it is illustrated in block 1120. If the question to be answered in block 1100 is answered by NO, however, an iterative step back is performed in order to examine the current values of n and sn in block 1030. If block 1030 is answered by YES sometime in the iteration, a step back to block 1140 is performed in which the reduction parameter b is set to zero. In the three operand operation illustrated in block 950 in FIG. 18 this leads to the fact that no modulus is added or subtracted, which means, that the intermediate result Z was so small that no modular reduction was required. In block 1160 the variable n is then newly allocated, wherein then finally in block 1180 the reduction shift value sn is calculated which is required in block 940 of FIG. 18 to perform the left shift of the modulus in order to obtain a shifted modulus.
In blocks 1200, 1220 and 1240 finally the current values of n and k are examined regarding further variables MAX and cur_k in order to examine the current allocation of the N register in order to guarantee that no register exceedings takes place. The further details are not important for the present invention, are, however, described in more detail in DE 3631992 C2.
The algorithm illustrated in FIGS. 18 and 19 may be implemented in hardware, as it is illustrated in FIG. 10. For the three operand operation to be performed in block 950 an arithmetical unit 700 is required which is referred to as AU in FIG. 10. The same is coupled to a register C 710 for the multiplicand, to a register N 720 for the modulus and to a register Z 730 for the current intermediate result of the modular multiplication. Form FIG. 10 it may further be seen that the result of the three operand operation is fed into the Z register 730 again via a feedback arrow 740. From FIG. 10 further the connection of the registers to each other may be seen. The value ZDN calculated in block 1020 of FIG. 19 needs to be saved in a separate ZDN register 750. The ZDN comparison or the iteration loop illustrated in FIG. 19, respectively, is further controlled in its operation by a separate control logic 760 for the ZDN comparison.
The main task of the ZDN algorithm for the calculation of Z:=M×C mod N further consists of the following two operations:    1. Calculation of the shift values sz and si for the registers Z and N, so that the following equation is satisfied:⅔N×2−si<|Z|≦ 4/3N×2−si and    2. Calculation of the three operand sum:Z:=2sZZ+aC+b×2sz-siN, 
The multiplication look-ahead parameter a and the reduction look-ahead parameter b may take values of −1, 0 and +1, as it is known.
It is to be noted that the intermediate result Z, the multiplicand C and the modulus N are long numbers, i.e. numbers whose number of digits or bits, respectively, may be greater than 512, wherein these numbers may have up to 2048 digits.
The above-described known method for performing the modular multiplication therefore comprises the following slightly rewritten three operand addition:N:=N*2sn Z:=Z*2sz+vc*C+vn*N. 
In the preceding equations sZ indicates the shift value of the intermediate result Z as it is calculated from the known Booth method, i.e. the multiplication look-ahead method. sn indicates the shift value of N as it is calculated and as it was performed above.
In one practical implementation the shift values sz and sn must not be infinitely high, because for this shifters for shifting long numbers are provided which can only carry out a bit shift in a long number register up to a maximum shift value. Therefore, in a cryptography processor which operates according to the known ZDN method, a shift value sz between 0 and 5 is enabled. With regard to the shifting of the modulus a shift value between −3 and +3 is used.
It is a disadvantage of the limited shift values that e.g. the shift value sz for shifting the intermediate result Z from a preceding iteration step is often too small for a current iteration step. This is the case when the multiplication look-ahead algorithm determines that the multiplier is implemented so that e.g. a greater shift value than 5 is possible. This is the case when depending on the look-ahead rule e.g. more than 5 successive zeros occur in the multiplier. If it is considered that the multiplier M comprises 1024 or even 2048 bits then this situation may easily occur frequently. Due to the limited shift value the known ZDN method will in this “special case” react by performing a three operand operation, with the maximum shift value, that, however, the multiplication look-ahead parameter vc is set to 0, i.e. that in this step nothing is added to the multiplicand. In the next iteration step a new multiplication shift value sz is calculated which is then, when it is greater than the maximum shift value szmax, limited by a maximum shift value, which again leads to a degenerated “three operand operation”, in which the multiplicand is again not added, in which therefore only the shifted intermediate result and the shifted modulus are added under consideration of the sign of the modulus.
From the preceding consideration it may be seen that in such as special case, when the multiplication look-ahead algorithm would allow a great shift, the same may not be implemented to achieve maximum efficiency due to the limited shift amount szmax.
The known ZDN method is therefore not able to use the full efficiency increase of the multiplication look-ahead method. In order to achieve an efficiency increase, in the known ZDN method a shifter increase would have to be preformed which, however, leads to the fact that more chip area is required, in particular with integrated circuits for chip-cards, which is not always tolerable due to restricted area provisions by chip-card manufacturers or may lead to considerable price increases, respectively.
It is to be noted here, that in particular in the field of cryptography processors a largely competitive market exists where already small price differences may lead to the survival of one supplier while the other supplier will not survive. The reason for this is that processors for chip-cards are a mass product as chip-cards are typically manufactured in great numbers.
On the other hand there are considerable security requirements for the chip-card processors, as chip-cards are typically in the hand of users, i.e. also in the hands of attackers, which have the chip-card processor to be attacked completely in their hands. Therefore security requirements for cryptography algorithms continuously increase, which for example becomes obvious through the fact that for increasing the security of the RSA algorithm the operands are no more only e.g. 1024 bit long but have to be 2048 bit long.
Anyway, the overall area required by the processor is firmly given by the chip-card manufacturer. This means that a manufacturer for chip-card processors must place arithmetic units and place-intensive memories on a firmly given area. On the other hand, increasingly compact cryptography algorithms also require more working memory, so that an enlargement of an arithmetic unit, so that e.g. a greater shifter is built in, is often not tolerable for this reason. If more chip area was given to the arithmetic unit, i.e. for example to a shifter, then on the other hand less working memory could be implemented on the firmly given chip area, which again leads to the fact that certain highly-complicated cryptography algorithms can not be implemented at all or are slower in calculating as if they were processed and implemented by rival products, respectively.
The known ZDN method explained with reference to FIGS. 18 and 19 is disadvantageous in so far that the three operand addition of the long-number calculating unit illustrated by block 950 in FIG. 18 may not continuously be processed but that always first a calculation of a look-ahead parameter sz′ sn and if necessary of the parameters a and b is to be carried out using blocks 910 and 930 before then the three operand addition may be performed. It is so to speak a serial two stage principle in an iteration loop, in so far that first look-ahead parameters are calculated and then the three operand addition is performed. During the calculation of the shift and sign parameters sz and sn or a and b, respectively, the calculating unit for performing the three operand addition runs idle, which is illustrated by block 950 in FIG. 18.